# PrimeRoots.py
# 求素数原根
# -*- coding: utf-8 -*-
"""
Created on 2021

@author: Ximing
"""


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


# 按定义求原根
def primeRoots(m):
    roots = []
    required_set = set()
    for num in range(1, m):
        if gcd(num, m) == 1:
            required_set.add(num)

    for g in range(1, m):
        actual_set = set()
        for powers in range(1, m):
            actual_set.add(pow(g, powers) % m)
        if required_set == actual_set:
            roots.append(g)
    return roots


# 使用定理快速的求原根
def quickPrimeRoots(m):
    coPri_set = set()  # 与m 互素 所组成的集合。
    for num in range(1, m):
        if gcd(num, m) == 1:
            coPri_set.add(num)

    primefactors = []  # p/q_i 所组成的集合。
    for num in range(1, m - 1):
        isPrime = 1
        for i in range(2, num):
            if (num % i) == 0:
                isPrime = 0
                break
        if gcd(m - 1, num) != 1 and isPrime == 1:
            primefactors.append(num)

    roots = []
    for g in coPri_set:
        isRoots = 1
        for q in primefactors:
            if pow(g, (m - 1) / q) % m == 1:
                isRoots = 0
                break
        if isRoots == 1:
            roots.append(g)
    return roots


if __name__ == "__main__":
    p = 17
    primitive_roots = primeRoots(p)
    print(primitive_roots)
    primitive_roots = quickPrimeRoots(p)
    print(primitive_roots)
